#include <stdio.h>
#include <iostream>
using namespace std;

int atoi(const char* a)
{
	if(!a || !*a)
		return 0;
	int i = 0;
	bool bNeg = false;
	if(*a == '-'){bNeg = true; a++;}
	while(*a)
	{
		(i *= 10) += *a++ - '0';
	}
	return bNeg? -i : i;
}

const char* itoa(int x)
{
	int i = x;
	int j = 0;
	do{i /= 10; j++;}while(i);

	if(x < 0)
		j += 2;
	else
		j += 1;
	x = x < 0 ? -x : x;
	char* a = new char[j];
	a[(--j)--] = '\0'; 
	do
	{
		a[j--] = "0123456789"[x % 10]; x /= 10;
	}while(x);

	if(j == 0)
		a[j] = '-';

	return a;
}

int mystrcmp (const char* a, const char* b)
{
	if(!a || !b)
	{
		if(!a && !b)
			return 0;
		if(!a)
			return *b;
		else 
			return *a;
	}
	while(*a == *b)
	{
		if(*a == '\0')
			return 0;
		a++; b++;
	}
	//different from regular string cmp
	//in that shorter substring is bigger
	if(!*a) return 1;
	if(!*b) return -1;
	return *a - *b;
}

void lexicographicSort(int arr[], int length)
{
	for(int i = 0; i < length; i++)
	{
		for(int j = 0; j < length - i - 1; j++)
		{
			if(mystrcmp(itoa(arr[j]), itoa(arr[j+1])) < 0)
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

const char* Concat(const char* a, const char* b)
{
	if(!a || !b)
	{
		if(!a && !b)
			return NULL;
		if(!a)
			return b;
		else
			return a;
	}

	char *temp = new char[strlen(a) + strlen(b) + 1];

	char *tracer = temp;
	while(*tracer++ = *a++); --tracer;
	while(*tracer++ = *b++);

	*tracer = '\0';
	return temp;
}

int LargestPossibleNumber(int arr[], int length)
{
	if(!arr || !length)
		return 0;
	const char *temp = NULL;

	lexicographicSort(arr, length);
	for(int i = 0; i < length; i++)
	{
		temp = Concat(temp,itoa(arr[i]));
	}
	return atoi(temp);
}

int MaxRectArea(int arr[], int length)
{
	if(!arr || !length)
		return 0;
	int MaxArea = 0;
	for(int i = 0; i < length; i++)
	{
		int area = 0;
		for(int j = i - 1; j > 0 && arr[j] >= arr[i]; j--)
		{
			area += arr[i];
		}
		for(int j = i; j <length && arr[j] >= arr[i]; j++)
		{
			area += arr[i];
		}
		if(area > MaxArea)
			MaxArea = area;
	}
	return MaxArea;
}


void main()
{
	int arr[] = {0,9,11,10,0,4,2,1,5,6,7};
	//cout << LargestPossibleNumber(arr, 6);
	cout << MaxRectArea(arr, sizeof(arr)/sizeof(int));
}
